package leetcode.每日一题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/11 10:08
 * @description :
 */
public class 最长递增子序列II {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.lengthOfLIS(new int[]{5, 7, -24, 12, 13, 2, 3, 12, 5, 6, 35})));
    }

    class Solution {
        public int[] lengthOfLIS(int[] nums) {
            int n = nums.length;
            if (n == 0) return null;
            int[] ans = new int[0];
            int len = 1;
            int[] d = new int[n + 1];
            d[len] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (d[len] < nums[i]) {
                    d[++len] = nums[i];
                    ans = Arrays.copyOfRange(d, 1, len + 1);
                } else {
                    int l = 1, r = len, pos = 0;
                    while (l <= r) {
                        int mid = l + r >> 1;
                        if (d[mid] < nums[i]) {
                            pos = mid;
                            l = mid + 1;
                        } else r = mid - 1;
                    }
                    d[pos + 1] = nums[i];
                }
            }
            return ans;
        }
    }

}
